Phân loại ngôn ngữ theo mô hình Chomsky Ngôn_ngữ_hình_thức

Mô hình phân cấp Chomsky. Cơ bản nhất là Regular, phức tạp nhất là Recursively Enumerable

Noam Chomsky (1928), một nhà triết học người Mỹ về ngôn ngữ và là giáo sư ngôn ngữ học tại MIT đã xây dựng lên một ý tưởng rằng "Loài người học ngôn ngữ không phải bắt đầu từ những hành vi (behavior) (là những phản ứng sự kích thích một cách có định hướng), mà nó dựa trên nhận thức và sự bẩm sinh"[1]. Bằng những nỗ lực để chứng minh học thuyết này, ông đã đưa ra một mô hình gọi là Mô hình phân cấp Chomsky.

Mô hình này gồm bốn loại ngôn ngữ và các gắn kết về ngữ pháp (grammar) và máy (machine):

  • Loại 0: Recursively Enumerable Languages (ngôn ngữ đếm được theo cách đệ quy)
  • Loại 1: Context-Sensitive Languages (ngôn ngữ phụ thuộc ngữ cảnh)
  • Loại 2: Context-Free Languages (ngôn ngữ không phụ thuộc ngữ cảnh)
  • Loại 3: Regular Languages (ngôn ngữ chính quy)